package top.minuy.structure.graph.cycle.directed;

import top.minuy.structure.graph.representations.table.Graph;

/**
 * 有向图环检测
 *
 * @author Minuy
 * @time 9:11
 * @date 2021/11/27
 */
public class DirectedCycleDetection {

    private Graph g;
    private boolean[] isVisited;
    private boolean[] isPath;
    private boolean hasCycle;

    public DirectedCycleDetection(Graph g) {
        this.g = g;

        if (!g.isDirected()) {
            throw new IllegalArgumentException("DirectedCycleDetection only works in directed graph.");
        }

        isVisited = new boolean[g.V()];
        isPath = new boolean[g.V()];

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                if (dfs(v)) {
                    hasCycle = true;
                    break;
                }
            }
        }
    }

    /**
     * 深度优先遍历
     *
     * @param v      当前顶点
     * @return boolean 是否检测到了环
     * @author Minuy
     * @date 2021/11/27 9:21
     */
    private boolean dfs(int v) {
        isVisited[v] = true;
        isPath[v] = true;

        for (int w : g.adj(v)) {
            if (isVisited[w]) { //被访问过了
                // 不是父顶点，且在同一路径上
                //对于有向图，{1->2,2->1}也是被认为是环，
                // 所以不需要检测父顶点
                // if (w != parent && isPath[w]) {
                if (isPath[w]) {
                    return true;
                }
            } else {
                // 深度优先遍历
                if (dfs(w)) {
                    return true;
                }
            }
        }

        isPath[v] = false; // 回溯
        return false;
    }


    /**
     * 查询这个图中有没有环
     *
     * @return boolean 有无环
     * @author Minuy
     * @date 2021/11/18 22:00
     */
    public boolean hasCycle() {
        return hasCycle;
    }

    @Override
    public String toString() {
        return String.valueOf(hasCycle());
    }

}
